#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/8/23 23:09
# @Author  : Yuyun
# @File    : leetcode_239_滑动窗口最大值.py
# @IDE     : PyCharm

"""
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：
输入：nums = [1], k = 1
输出：[1]

提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
"""

from collections import deque

class MyQueue:
    def __init__(self):
        self.queue = deque()
    def pop(self, value):
        if self.queue and self.queue[0] == value:
            self.queue.popleft()
    def push(self, value):
        #   单调队列最后一位值 小于 push值，推出
        while self.queue and self.queue[-1] < value:
            self.queue.pop()
        #保持队列从大到小
        self.queue.append(value)
    def max(self):
        return self.queue[0]

class Solution:
    #   暴力法，时间复杂度O（n * k）
    def max_in_slide_window(self, nums, k):
        length = len(nums)
        #初始化长度 length - k + 1的结果数组，值取无穷小
        nums_max = [float('-inf')] * (length - k + 1)
        for i in range(length - k + 1):
            left = i
            right = i + k
            #窗口大小k，取值从num[i] ~ num[i + k - 1]
            while left < right:
                if nums[left] > nums_max[i]:
                    nums_max[i] = nums[left]
                left += 1
        return nums_max
    #   单调队列实现
    def max_in_slide_window_I(self,nums, k):
        queue = MyQueue()
        result = []
        #   前k个元素的单调队列
        for i in range(k):
            queue.push(nums[i])
        result.append(queue.max())
        #   大小为k的窗口向后移动，一位一位向后移动
        for i in range(k, len(nums)):
            #推出最前一位，若不在单调队列中，则不做操作
            queue.pop(nums[i - k])
            #压入新一位，若新一位为最大值，单调队列前面元素清空
            queue.push(nums[i])
            result.append(queue.max())
        return result

if __name__ == '__main__':
    nums = list(map(int, input().split(',')))
    k = int(input())
    solution = Solution()
    result = solution.max_in_slide_window_I(nums, k)
    print(result)